package com.cn.algorithm02.class16;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/***
 * @author: hels
 * @description:  使用hashMap实现并查集，操作时间常数不如用数组实现
 **/
public class C01_UnionFind {

    public static class Node<V> {
        public V value;
        public Node(V value) {
            this.value = value;
        }
    }
    /**
     * 构造方法
     */
    public static class UnionSet<V> {
        //  对象Map
        HashMap<V, Node<V>> nodes;
        // node节点父子关系容器，key为节点自己，value为节点父亲；父亲节点指向自己；
        HashMap<Node<V>, Node<V>> parents;
//      父亲节点的大小，只有父亲节点才可以出现在该容器中
        HashMap<Node<V>, Integer> sizeMap;

//      构造方法
        public UnionSet(List<V> values) {
            nodes = new HashMap<>();
            parents = new HashMap<>();
            sizeMap = new HashMap<>();
            for (int i = 0; i < values.size(); i++) {
               Node<V> node = new Node<>(values.get(i));
               nodes.put(values.get(i), node);
               parents.put(node, node);
               sizeMap.put(node, 1);
            }
        }

        /**
         * 查找同一个域的祖宗节点
         * @param node
         * @return 祖宗节点
         */
        public Node<V> findAncestor(Node<V> node) {
            Stack<Node<V>> stack = new Stack<>();
            while (node != parents.get(node)) {
                stack.add(node);
                node = parents.get(node);
            }
            // 优化，将同一个集合的所有节点连接到祖宗节点上
            while (!stack.isEmpty()) {
                parents.put(stack.pop(), node);
            }

            return node;
        }
        /**
         * 判断是否是同一个域，返回boolean
         */
        public boolean isSameSet(V a, V b) {
            return findAncestor(nodes.get(a)) == findAncestor(nodes.get(b));
        }
        /**
         * 将两个域进行合并
         */
        public void union(V a, V b) {
            Node<V> aNode = nodes.get(a);
            Node<V> bNode = nodes.get(b);
            Node<V> ahead = findAncestor(aNode);
            Node<V> bhead = findAncestor(bNode);
            // 判断是否是同一个域
            if (ahead != bhead) {
                int aSize = sizeMap.get(ahead);
                int bSize = sizeMap.get(bhead);
                Node<V> max = aSize > bSize ? ahead : bhead;
                Node<V> small = max == bhead ? ahead : bhead;
//                小的指向大的
                parents.put(small, max);
//                大的节点，size增大；小的节点从sizeMap中删除
                sizeMap.put(max, aSize + bSize);
                sizeMap.remove(small);
            }
        }

        @Override
        public String toString() {
            return "UnionSet{" +
                    "nodes=" + nodes +
                    ", parents=" + parents +
                    ", sizeMap=" + sizeMap +
                    '}';
        }
    }

    public static void main(String[] args) {
        List<Integer> al = new ArrayList<>();
        al.add(1);
        al.add(2);
        al.add(3);
        al.add(4);
        al.add(5);
        UnionSet<Integer> aSet = new UnionSet<>(al);
        System.out.println(aSet.isSameSet(2, 5));
        aSet.union(1,5);
        aSet.union(1,2);
        System.out.println(aSet.isSameSet(2, 5));
    }
}
